Implementing C# custom expression evaluator through RPN

• Download source - 4.15 Kb

Introduction

While studying applied math, I had never thought one day I’ll happen to use RPN in my professional developments. However, by the power of all-existent Murphy’s Law, I’ve got such a chance and here I’d like to share some results of the case.

Problem definition

To keep it simple, let’s assume we have a string containing arithmetic expression, where each operand is defined as (1), and available set of operations is defined as (2):

1. ^[{](\d+|\d+[\.]\d+){1}[}]$
2. ^[+|-|*|/]$

The order of computation can change by putting some braces.

There is a need to evaluate the string and get some numeric result. The original problem (real life) was based upon following suggestions: having template string e.g. {sum1}-({sum2} + {sum3} / {sum4}) and appropriate sumN values, calculate the expression.

Implementation snippets

The overall idea of implementation is to use Reverse Polish Notation algorithm through stack. So the realization steps can be divided onto:

1. getting RPN representation of the string (it will contain ‘{‘ & ‘}’ as number boundaries delimiters)
2. calculating RPN expression preserving operations precedence

The code attached to article contains algorithm implementation as part of simple console project aimed to test evaluation functionality.

Here I’ll put some focus on selected code blocks (since details are much easily seen within context, IMHO it’s always a better way investigating a complete code):

1. the operations’ precedence is defined in IsLeftWeaker and IsLeftStronger code blocks as follows:

       private static bool IsLeftWeaker(char lop, char rop) {
         return ((lop=='+' || lop=='-') && (rop=='/' || rop=='*'));
       }
       private static bool IsLeftStronger(char lop, char rop) {
         return (((lop=='/' || lop=='*') && 
             (rop=='+' || rop=='-')) || rop=='(');
       }
   

2. the actual RPN realization:

       private static string GetRPN(string expression) {
         Stack stOps = new Stack();
         StringBuilder sbRpn = new StringBuilder();
         for(int i=0; i<expression.Length; i++) {
           if(IsOperand(expression[i])) {
             sbRpn.Append(expression[i]);
           }else
             if(IsOperation(expression[i])) {
             if(stOps.Count==0) {
               stOps.Push(expression[i]);
             }else{
               if(CompareOperations(expression[i], 
                    (char)stOps.Peek())) {
                 sbRpn.Append((char)stOps.Pop());
               }
               stOps.Push(expression[i]);
             }
           }else
             if(IsBracket(expression[i])) {
             if(expression[i]=='(') {
               stOps.Push('(');
             }else{  
               while(stOps.Count>0 && (char)stOps.Peek()!='(') {
                 sbRpn.Append((char)stOps.Pop());
               }
               stOps.Pop();//just like a trash
             }
           }else{
             throw new ArgumentOutOfRangeException("expression", 
                   "Wrong parameter value!");
           }
         }
         while(stOps.Count>0) {
           sbRpn.Append((char)stOps.Pop());
         }
         return sbRpn.ToString();
       }
   

3. and evaluation itself:

       public static double Eval(string expression) {
         string rpn = GetRPN(expression);
         Console.WriteLine("rpn: " + rpn);
         Stack stVals = new Stack();
         RPNEnumerator rpnEnum = new RPNEnumerator(rpn);
         while(rpnEnum.MoveNext()) {
           RPNValue rpnVal = (RPNValue)rpnEnum.Current;
           if(rpnVal.type==RPNValueType.OPERAND) {
             stVals.Push(Double.Parse(rpnVal.val, 
                  new CultureInfo("en-US")));
           }else{
             double v2 = (double)stVals.Pop();
             double v1 = (double)stVals.Pop();
             if(rpnVal.val=="+") {
               stVals.Push(v1+v2);
             }else
               if(rpnVal.val=="-") {
               stVals.Push(v1-v2);
             }else
               if(rpnVal.val=="*") {
               stVals.Push(v1*v2);
             }else
               if(rpnVal.val=="/") {
               stVals.Push(v1/v2);
             }
           }
         }
         return (double)stVals.Pop();
       }
   

Please pay attention to mechanism of navigation through RPN string – I’ve integrated custom iterator for moving through ‘{‘/ ‘}‘-braced data and operations, so the IEnumerator.MoveNext looks like this:

    public bool MoveNext() {
      bool result = false;
      if(_rpn.Length>_index) {
        string val = String.Empty;
        RPNValue rpnVal = new RPNValue();
        if(_rpn[_index]=='{') {
          _index++;
          while(_rpn[_index]!='}') {
            val+=_rpn[_index].ToString();
            _index++;
          }
          rpnVal.val = val;
          rpnVal.type = RPNValueType.OPERAND;
        }else{
          rpnVal.val = _rpn[_index].ToString();
          rpnVal.type = RPNValueType.OPERATION;
        }
        _current = rpnVal;
        _index++;
        result = true;
      }
      return result;
    }

Some results

To illustrate code "in action", you'll have to get a source here (4.15 Kb zip) or just believe in this shot:

This is evaluation result for test expression "{1.2}+({2}+{3.24}*{2.3})/{5}"